// https://leetcode.cn/problems/duplicate-zeros/description/

// 算法思路总结：
// 1. 使用双指针计算最终位置：cur遍历原数组，dest计算目标位置
// 2. 遇到非零元素：dest前进1步；遇到零元素：dest前进2步（需要复制）
// 3. 处理边界情况：当最后一个零复制后可能超出数组长度时需要特殊处理
// 4. 从后向前进行填充操作：避免覆盖未处理的元素
// 5. 遇到零时复制两个零，遇到非零时直接复制
// 6. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int dest = -1, cur = 0, n = arr.size();

        while (cur < n && dest < n)
        {
            if (arr[cur]) 
                dest++;
            else 
                dest += 2;

            if (dest >= n - 1) 
                break;
            cur++;
        }

        if (dest == n)
        {
            arr[dest - 1] = 0;
            dest -= 2;
            cur--;
        }

        while (cur >= 0)
        {
            if (arr[cur])
            {
                arr[dest] =  arr[cur];
                dest--;
            }
            else
            {
                arr[dest] = arr[dest - 1] = 0;
                dest -= 2;
            }
            cur--;
        }
    }
};

int main()
{
    vector<int> v1 = {1,0,2,3,0,4,5,0};
    vector<int> v2 = {1,2,3};

    Solution sol;
    sol.duplicateZeros(v1);
    sol.duplicateZeros(v2);

    for (auto& val : v1) cout << val << " ";
    cout << endl;
    for (auto& val : v2) cout << val << " ";
    cout << endl;

    return 0;
}